% !TEX TS-program = pdflatex
% !TEX encoding = UTF-8 Unicode

% This is a simple template for a LaTeX document using the "article" class.
% See "book", "report", "letter" for other types of document.

\documentclass[11pt,a4paper,french]{article} % use larger type; default would be 10pt

\usepackage[frenchb]{babel}

\usepackage[utf8]{inputenc} % set input encoding (not needed with XeLaTeX)

%%% Examples of Article customizations
% These packages are optional, depending whether you want the features they provide.
% See the LaTeX Companion or other references for full information.

%%% PAGE DIMENSIONS
%\usepackage{geometry} % to change the page dimensions
%\geometry{a4paper} % or letterpaper (US) or a5paper or....
% \geometry{margins=2in} % for example, change the margins to 2 inches all round
% \geometry{landscape} % set up the page for landscape
%   read geometry.pdf for detailed page layout information

\usepackage{graphicx} % support the \includegraphics command and options

% \usepackage[parfill]{parskip} % Activate to begin paragraphs with an empty line rather than an indent

%%% PACKAGES
\usepackage{booktabs} % for much better looking tables
\usepackage{array} % for better arrays (eg matrices) in maths
\usepackage{paralist} % very flexible & customisable lists (eg. enumerate/itemize, etc.)
\usepackage{verbatim} % adds environment for commenting out blocks of text & for better verbatim
\usepackage{subfig} % make it possible to include more than one captioned figure/table in a single float
% These packages are all incorporated in the memoir class to one degree or another...

%%% HEADERS & FOOTERS
\usepackage{fancyhdr} % This should be set AFTER setting up the page geometry
\pagestyle{fancy} % options: empty , plain , fancy
\renewcommand{\headrulewidth}{0pt} % customise the layout...
\lhead{}\chead{}\rhead{}
\lfoot{}\cfoot{\thepage}\rfoot{}

%%% SECTION TITLE APPEARANCE
\usepackage{sectsty}
\allsectionsfont{\sffamily\mdseries\upshape} % (See the fntguide.pdf for font help)
% (This matches ConTeXt defaults)

%%% ToC (table of contents) APPEARANCE
\usepackage[nottoc,notlof,notlot]{tocbibind} % Put the bibliography in the ToC
\usepackage[titles,subfigure]{tocloft} % Alter the style of the Table of Contents
\renewcommand{\cftsecfont}{\rmfamily\mdseries\upshape}
\renewcommand{\cftsecpagefont}{\rmfamily\mdseries\upshape} % No bold!
\newcommand{\HRule}{\rule{\linewidth}{0.5mm}}
%%% END Article customizations

%%% The "real" document content comes below...

%\title{Rapport - Moteur de Recherche}
%\author{Olivier Chenevotot \and Quentin Dorveaux \and Quentin Galvane \and Thibaud Guilpain \and  Thibault Le Meur \and Germain Potet \and Baptiste Uzel}
%\date{} % Activate to display a given date or no date (if empty),
         % otherwise the current date is printed 

\begin{document}
\begin{titlepage}

\begin{center}   


\textsc{\Large Projet d'Acquisition de Connaissances}\\[0.5cm]


% Title
\HRule \\[0.4cm]
{ \huge \bfseries Mise en oeuvre d'un moteur de recherche et évaluation}\\[0.4cm]

\HRule \\[1.5cm]

% Author and supervisor
\begin{minipage}{0.4\textwidth}
\begin{flushleft} \large
\emph{Auteurs:}\\
Olivier \textsc{Chenevotot}\\
Quentin \textsc{Dorveaux}\\
Quentin \textsc{Galvane}\\
Thibaud \textsc{Guilpain}\\
Thibault \textsc{Le Meur}\\
Germain \textsc{Potet}\\
Baptiste \textsc{Uzel}
\end{flushleft}
\end{minipage}
\begin{minipage}{0.4\textwidth}
\begin{flushright} \large
\emph{Superviseurs:} \\
Pascale \textsc{Sébillot}\\
\end{flushright}
\end{minipage}

\vfill

% Bottom of the page
{\large \today}
\end{center}

\begin{flushright}
	\includegraphics[scale=0.70]{insa.png}\\[1cm]    
\end{flushright}
\end{titlepage}

%\maketitle

\tableofcontents
\pagebreak
\section{Introduction}

\paragraph{}
\`{A} travers ce projet d’acquisition de connaissances de 4\ieme~année, nous avons réalisé un moteur de recherche. Ce moteur de recherche permet aux utilisateurs, à l’aide de simples requêtes, de trouver les articles répondant de la façon la plus pertinente possible aux requêtes en question. La bibliothèque d'articles à parcourir est fournie sous forme d’un seul fichier texte et est donc traitée avant de pouvoir être utilisée efficacement par notre moteur de recherche.
\paragraph{}
Pour réaliser ce projet, nous sommes donc passés par différentes phases de réflexions avant de coder celui-ci. Tout d’abord, nous nous sommes penchés sur le langage d’implémentation que nous pourrions utiliser. Nous avons ensuite réalisé un diagramme de classes assez simple, qui nous a permis de nous pencher sur certains choix d’implémentation. \`{A} partir de ces éléments, nous avons enfin pu commencer le développement de notre moteur de recherche.
\paragraph{}
Pour finir, nous avons testé notre programme en évaluant la pertinence des résultats de notre requête à l'aide d'un autre fichier fourni pour le projet. Nous avons donc pu discuter et débattre de nos résultats et envisager d'autres solutions qui nous permettrait d'améliorer l'efficacité de notre recherche.

\section{Choix du langage}
\paragraph{}
L’un des premiers points sur lesquels nous nous sommes penchés est le choix du langage d’implémentation. Afin de nous décider, nous avons simplement réalisé une liste de critères qui nous aura aidés lors de cette prise de décision impactant tout notre projet.
Parmi ces critères figurent la maîtrise globale du langage par l’ensemble du groupe, la simplicité d’utilisation des expressions régulières, la facilité d’utilisation des différentes structures de données qui peuvent nous être utiles, ainsi que les langages dans lesquels le stemmer de Porter est implémenté. Certains langages comme OCaml ou Prolog qui nous étaient apparus comme originaux et envisageables pour un tel projet ont finalement rapidement été évincés de notre liste de choix du fait qu'ils ne permettent pas l'utilisation simple et intuitive de structures de données nécessaires à ce genre de projet.
\paragraph{}
\`{A} partir de tous les langages que nous envisagions, nous avons réalisé le tableau ci-dessous permettant de simplement les comparer à partir des différents critères précédemment cités.

\begin{table}[h!]
	\begin{center}
		\begin{tabular}{|l|c|c|c|c|c|}
			\hline
			Langage & Maîtrise du & Simplicité & Expressions & Structures & Stemmer\\
			         & langage &  d'utilisation &  régulières &  de données &  existant\\
			\hline
			C\# & + & + & ++ & ++ & +\\
			C++ & ++ & + & ++ & +++ & +\\
			Java & +++ & + & ++ & +++ & +\\
			Perl & ++ & ++ & +++ & + & +\\
			PHP & ++ & +++ & +++ & + & +\\
			Ruby & - & ++ & + & ? & + \\
			\hline
		\end{tabular}
	\end{center}
	\caption{Table de comparaison des langages}
\end{table}

\paragraph{}
Enfin, de ce tableau, deux langages sont ressortis~: Java et PHP. Bien que PHP soit particulièrement simple d'utilisation et que les expressions régulières soient très simples à utiliser (elles sont généralement faciles à utiliser dans les langages de script), nous avons finalement décidé d’utiliser Java pour implémenter notre projet en raison d'une meilleure maîtrise de ce langage par la majorité du groupe, de la présence d'un éventail de structures de données plus important, ainsi qu'un découpage plus aisé de l'application.


\section{Architecture générale}

\paragraph{}
Dans un deuxième temps, nous nous sommes attelés à modéliser notre application afin de faciliter son implémentation future. Pour cela, nous nous sommes concentrés à l'élaboration d'un diagramme de classes (voir figure~\ref{uml}).

\paragraph{}
Sur ce diagramme, nous constatons un découpage assez simple des différents acteurs~:
\begin{itemize}
 \item \textit{TabacPresse}~: classe principale de notre projet~;
 \item \textit{Enregistrement, Requete, Article}~: contient les informations tirées des fichiers fournis~;
 \item \textit{Indexeur}~: analyse les documents en entrée.
\end{itemize}

\subsection{TabacPresse}

\paragraph{}
Cette classe constitue la classe principale de notre projet. C'est elle qui lance l'indexation de l'ensemble des articles 
et qui maintient les structures de données nécessaires à cette opération. Une fois l'indexation achevée, il est possible 
de produire le fichier inversé (premier objectif). De m\^eme cette classe dispose de méthodes permettant de lancer
des recherches dans la base de données (second objectif).

\subsection{Enregistrement, Requete, Article}

\paragraph{}
Les classes \emph{Requete} et \emph{Article} représentent respectivement le contenu d'une requête et d'un article. Ces objets sont très similaires puisqu'ils contiennent
tous deux un numéro qui sert d'identifiant ainsi qu'une suite de termes pondérés. Afin d'éviter la redondance du code, nous avons décidé d'abstraire ces caractéristiques
en une seule classe nommée \emph{Enregistrement}.

\subsection{Indexeur}

\paragraph{}
Cette classe est utilisé par la classe \emph{TabacPresse} pour générer les instances d'\emph{Article} et de \emph{Requete}. 
Le comportement de cette classe est détaillé par la suite.

\begin{figure}[h!]
 \includegraphics[angle=90, height=19cm]{uml}
 \caption{Diagramme de classes du moteur de recherche}
 \label{uml}
\end{figure}



\section{Choix d’implémentation}
\paragraph{}
Lors du développement, nou	s nous sommes évidemment retrouvés confrontés à de nombreux choix d'implémentation. Dans cette partie, nous reviendrons donc sur ces différents choix effectués ainsi que sur les différentes méthodes mises en \oe uvre pour la réalisation de notre moteur~: 
\begin{itemize}
\item{Indexation des documents}
\item{Suppression des tokens inutiles}
\item{Pondération normalisée des mots par article}
\item{Pondération logarithmique}
\item{Interrogation}
\end{itemize}
\subsection{Indexation des documents}

\paragraph{}
Le mécanisme d'indexation est un composant clé dans la conception d'un moteur de recherche. 
Cette phase consiste en l'analyse de l'ensemble des documents dont on dispose et plus précisémment, elle cherche à dégager les termes
importants qui sont caractéristiques de chaque article. Au sein de la base de données du moteur, les documents analysés seront référencés par ces
termes (faisant office de clés de l'index) de sorte que la recherche d'articles liés à une requête puisse etre résolue le plus rapidement possible.
En clair, l'indexation est une étape de ``vectorialisation'' qui permet de structurer une bibliothèque d'articles.
Bien évidemment, le simple fait de relever les termes important ne suffit pas, il faut également donner un poids relatif à chacun des mots. Nous verrons
cela en détail un peu plus tard.

\paragraph{}
Dans cette partie, nous allons expliquer nos choix au niveau de l'indexation des documents.

\subsubsection{Description de la composition d'un article}
Voici ci-dessous un exemple d'article :\\
\begin{verbatim}
    .I 1
    18 Editions of the Dewey Decimal Classifications
       The present study is a history of the DEWEY Decimal
    Classification.  The first edition of the DDC was published
    in 1876, the eighteenth edition in 1971, and future editions
    will continue to appear as needed.  In spite of the DDC's
    long and healthy life, however, its full story has never
    been told.  There have been biographies of Dewey
    that briefly describe his system, but this is the first
    attempt to provide a detailed history of the work that
    more than any other has spurred the growth of
    librarianship in this country and abroad.
\end{verbatim}

\paragraph{}
Comme on peut le constater, la forme des documents à indexer est assez particulière et facilement reconnaissable~:\\
Tout d'abord, on peut voir que l'article commence par un numéro qui sert d'identifiant~; ici, on a \textit{.I 1} où \textit{1} correspond à l'identifiant de l'article en question. La ligne suivante correspond au titre~; ici, on a~: \textit{18 Editions of the Dewey Decimal Classifications}. La suite du texte est le contenu de l'article.

\subsubsection{Nos choix pour l'indexation}
\paragraph{Indexeur}
\paragraph{}
L'$Indexeur$, lorsqu'il ouvre le fichier contenants les articles (\textit{CISI.ALLnettoye}) va créer des instances de la classe \textit{Article}. Pour cela, il commence par récuperer la première ligne d'un article, donc son numéro. Il crée alors un nouvel article avec comme identifiant ce numéro et parse ensuite le reste de l'article (titre et corps de l'article) en séparant chacun des mots le composant. De cette suite de mots on élimine tous les mots grammaticaux qui ne sont la que pour structurer la phrase (ces mots sont répertoriés dans le fichier \textit{motsvides.txt}). Enfin, on applique éventuellement un procédé de stemming (qui transforme les flexions en leur radical, aussi appelé racinisation).
\paragraph{Article}
\paragraph{}
Un article est représenté par une instance de la classe $Article$. Un article est identifée par un entier ($id$). Chaque instance de cette classe possède deux $HashMap$~:
\begin{itemize}
\item $frequenceMots$ : associe chaque mot stemmé de l'article à une fréquence dans cette article~;
\item $motsPonderes$ : associe chaque mot à sa valeur pondérée normale dans l'article. 
\end{itemize}
\paragraph{}
Les $HashMap$ ont la particularité d'éviter les doublons lorsqu'on ajoute un élément dont la clé est déjà existante. De plus, l'indexation dans celles-ci est très efficace et nous permet de retrouver les mots, leur fréquence et leur pondération facilement et rapidement. Nous trouvons aussi un entier $nbMots$ qui représente le nombre de mots dans l'article (sans les stopwords) et un nombre flottant pour connaître la fréquence maximale d'un mot dans l'article.
\paragraph{TabacPresse}
\paragraph{}
Pour faciliter le stockage des articles indéxés, nous avons créé une classe \emph{Couple} qui permet d'associer à un article 
(identifié par l'attribut \emph{key}) une pondération (attribut \emph{value}). La classe \emph{TabacPresse} dispose de tables 
de hachage qui à un mot donné associent une liste contenant des objets de type \emph{Couple} qui sont autant d'articles contenant
ce mot. Les listes associées à chaque mot sont ordonnées suivant la pondération des objets \emph{Couple}. Cela permet lors d'une
recherche de disposer le plus rapidement possible des articles qui sont les plus pertinents vis à vis d'un mot donné.

\subsection{Suppression des tokens inutiles et stemmatisation}
\paragraph{}
De nombreux mots ne sont pas pertinents pour indexer un article, nous avons donc utilisé une liste regroupant un nombre important de mots communs n'ayant pas de grande importance sur le sujet général de l'article. Ainsi, de la phrase $He is in the blue garden$, nous n'indexerons que $blue garden$. Il peut être intéressant d'utiliser un stemmer pour mieux cibler le sens d'un article. Par exemple, les termes $Worked$, $Working$, $Works$ et $Work$ partagent la même racine et parlent tous de travail. Le stemmer que nous utilisons se charge également de supprimer les particules lors de l'indexation des documents.

\subsection{Pondération normalisée des mots par article}
\paragraph{}
Dans un premier temps, nous avons réalisé une pondération à partir de la fréquence d'apparition des termes normalisée. La formule suivante décrit le calcul de la pondération~:
\[w(t_i) = \frac{tf(t_i)}{max(tf(t))}\]
où $tf(t_i)$ est la fréquence du terme $t_i$ dans le document traité et $max(tf(t))$ la plus forte fréquence d'un terme dans ce document.
\paragraph{}
Cette méthode de pondération permet d'accorder autant d'importance aux petits articles qu'aux grands. Cependant, elle ne tient pas compte du nombre de documents de la collection.


\subsection{Pondération logarithmique}
\paragraph{}
Dans un second temps, nous avons réalisé la pondération des termes par fréquence logarithmique. La formule suivante a été utilisée pour le calcul de cette pondération~:
\[w(t_i) = tf(t_i) \cdot log\left(\frac{N}{df(t_i)}\right)\]
où $N$ est le nombre de documents de la collection et $df(t_i)$ le nombre de documents de la collection contenant $t_i$.
\paragraph{}
Cette méthode de pondération permet quant à elle de tenir compte du nombre de documents de la collection 
afin de pondérer la fréquence et obtenir des résultats plus pertinents.


\subsection{Interrogation}

Nous avons également pondéré les requêtes de la même manière que pour les documents. Afin de pouvoir procéder à une interrogation, nous mesurons la similarité entre le vecteur d'indexation de la requête et ceux des documents. Nous ordonnons alors la liste de documents récupérés par ordre de pertinence.

\section{\'{E}valuation}
\paragraph{}
Maintenant que notre moteur de recherche nous retourne une liste ordonnée d'articles, il est intéressant de s'interroger sur la pertinence de ce résultat.
\paragraph{}
Dans un premier temps, un moyen simple de tester notre moteur de recherche est de lancer une requête et d'observer les résultats obtenus en consultant les articles rendus. Cette première solution, bien que simple, s'avère rapidement fastidieuse du fait du grand nombre d'articles retournés pour certaines requêtes. Cependant, via ce premier moyen, nous avons pu vérifier que les requêtes formulées retournaient bien des résultats cohérents. Ainsi, pour une requête donnée, on peut constater que les articles rendus comportent bien au moins l'un des mots de la requête. De plus, après quelques parcours d'articles, on peut constater que la valeur associée à chaque article pour une requête donnée (correspondant en quelque sorte à la pertinence de l'article) semble cohérente. Ainsi, les articles contenant beaucoup de mots de la requête ont une valeur associée élevée et, au contraire, les articles peu pertinents ont des valeurs associées assez faibles. Voici ci-dessous un exemple de requête et une partie du résultat obtenu pour chacune des deux pondérations précedemment présentées~:


\begin{verbatim}
  Requête : What problems and concerns are there in making up descriptive titles? 
    Recherche normalisée :
    7 (0.3333333333333333) 
    9 (0.33333333333333337)
    11 (0.3333333333333333)
    12 (0.25)
    16 (0.25)
    17 (0.6000000000000001)
    25 (0.25) 
\end{verbatim}

\begin{verbatim}
    Recherche par Pondération Logarithmique :
    7 (0.038951292809305545)
    9 (0.021850725234488475)
    11 (0.03380678243826519)
    12 (0.01990843854697839)
    16 (0.028581490602202986)
    17 (0.0277076206581658)
    25 (0.05192956850890211)
\end{verbatim}


On constate que les deux méthodes de pondération rendent des résultats différents. On voit par exemple que l'article 17 pour la pondération normalisée semble correspondre à la requête alors que les autres articles sont moins pertinents. Et d'après la méthode de pondération logarithmique, c'est l'article 25 qui est le plus pertinent. Les deux méthodes de pondérations se basant sur des critères différents, il est normal que les résultats le soient également.

\paragraph{}
L'autre solution qui nous permettrait d'évaluer notre moteur de recherche se base sur la comparaison de nos résultats avec le fichier \textit{CISI.REL} fourni. Cependant, le fichier en question semble incomplet et ne donne aucune information sur les jugements de pertinence pour chaque reqûete. Ce fichier nous aurait permis de comparer chacune des méthodes et de vérifier leur exactitude.

\paragraph{}
Afin d'améliorer la pertinence des résultats renvoyés, nous pourrions mettre en place une autre forme de pondération qui considérerait par exemple le titre comme plus important et augmenterait la valeur associée à un article pour une requête donnée si certains mots de la requête sont situés dans le titre.

\section{Conclusion}
%EBAUCHE DE CONCLUSION
\paragraph{}
En conclusion de ce rapport, nous pouvons dire que ce projet nous a permis de mettre en application les enseignements d'acquisition de connaissances.
\paragraph{}
La phase de réflexion a été importante, en commençant par le choix du langage. Nous sommes allés vers celui que nous maîtrisions le mieux~: Java. Les structures de données sont claires, et l'approche objet nous permet de découper notre application de manière claire et structurée.
\paragraph{}
La modélisation s'est ensuite déroulée sans problème, le sujet nous guidant au fur et à mesure des étapes. Le découpage s'est fait en trois classes principales~: \textit{Indexeur}, \textit{Article} et \textit{TabacPresse}. Nous avons donc mis en application les techniques présentées en cours, à savoir la stemmatisation, l'indexation, et la pondération.
\paragraph{}
Enfin, nous avons pu comparer les résultats obtenus par les différentes méthodes de pondération. Ces deux méthodes, bien que différentes, donnent des résultats tout à fait cohérent.
% A finir
\end{document}
